package JianZhiOffer;

//斐波那契数列
public class numWays {

    public int numWays(int n) {
        // 注和fib不一样
        if (n <= 1) {
            return 1;
        }

        int a = 1, b = 1, sum = a + b;
        for (int i = 2; i < n; i++) {
            a = b;
            b = sum;
            sum = (a + b) % 1000000007;
        }
        return sum;
    }
}
